package X的平方根;

/**
 * X的平方根，得到x的平方根的整数部分
 * 二方法、牛顿迭代
 */
public class Solution {
    public static void main(String[] args) {

        int num = 6;

        int v = binarySearch(num);
        System.out.println("binarySearch = " + v);

        v = newton(num);
        System.out.println("newton = " + v);
    }

    /**
     * 二分法
     */
    public static int binarySearch(int num) {
        int l = 0, r = num;
        int index = -1;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (mid * mid <= num) {
                index = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }

        return index;
    }

    /**
     * 牛顿迭代
     */
    public static int newton(int num) {

        if (0 == num) {
            return 0;
        }

        return (int) sqrt(num, num);
    }

    public static double sqrt(double x, int n) {
        // 关键点 求 n-x的平方根
        double r = (x + n / x) / 2;
        if (r == x) {
            return r;
        }
        return sqrt(r, n);
    }
}
